#!/usr/bin/python
# Filename: List.py

# class of List in both sequential and linked form.
# from now on, we use _S postfix to represent sequential form ADT.
# but List is an exception, bcz linked List is called LinkedList.


class List:

    def __init__(self, max_length=10):
        self.items = [None] * max_length
        self.max_length = max_length
        self.length = 0
        self.curr = -1

    def __del__(self):
        # embedded objects are automatically freed when parent is (unless referenced from elsewhere).
        # and reference count will also help freeing objects.
        pass

    def __str__(self):
        return str(self.items[:self.length]) + " : " + str(self.curr)

    def clear(self):
        del self.items[:]
        self.curr = -1

    def set_first(self):
        if self.length > 0:
            self.curr = 0
            return True
        else:
            return False

    def prev(self):
        if self.curr > 0:
            self.curr -= 1
            return True
        else:
            return False

    def next(self):
        if self.curr < self.length -1:
            self.curr += 1
            return True
        else:
            return False

    def __contains__(self, value):
        # it is value, not item.
        # bcz what compared are only references if the values are a reference to compound DSes
        if value in self.items:
            return True
        else:
            return False

    def append(self, value):
        if self.length == self.max_length:
            return False
        self.items[self.length] = value
        self.length += 1
        return True

    def insert(self, value, pos=None):
        if pos == None: pos = self.curr
        if pos > self.length or self.length == self.max_length or pos < 0:
            return False
        for i in range(self.length, pos, -1):
            self.items[i] = self.items[i-1]
        self.items[pos] = value
        self.length += 1
        return True

    def remove(self, pos=None):
        if pos == None: pos = self.curr
        if pos < 0 or pos >= self.length:
        # self.length > 0 is hint by pos >= 0 and pos < self.length
            return None
        value = self.items[pos]
        for i in range(pos, self.length-1):
            self.items[i] = self.items[i+1]
        self.items[self.length-1] = None
        self.length -= 1
        if self.curr == self.length:
            self.curr -= 1
        return value

    def is_empty(self):
        if self.length:
            return False
        else:
            return True

    def curr_value(self):
        if self.curr == -1:
            return None
        else:
            return self.items[self.curr]


if __name__ == "__main__":
   l = List()
   print l
   print "l.is_empty():", l.is_empty()
   print "l.set_first():", l.set_first()
   print "l.insert(1, 1):", l.insert(1, 1)
   print "l.insert(1):", l.insert(1)
   print "l.insert(1, 0):", l.insert(1, 0)
   print l
   print "l.is_empty():", l.is_empty()
   print "l.curr_value():", l.curr_value()
   print "l.set_first():", l.set_first()
   print "l.curr_value():", l.curr_value()
   print "l.next():", l.next()
   print "l.prev():", l.prev()
   print l
   print "l.append(2):", l.append(2)
   print l
   print "l.insert(3, -1)", l.insert(3, -1)
   print "l.insert(4, 2)", l.insert(4, 2)
   print l
   print "l.insert(3, 2)", l.insert(3, 2)
   print l
   print "l.next():", l.next()
   print l
   print "l.remove():", l.remove()
   print l
   print "l.remove(2):", l.remove(2)
   print l
   print "l.remove(2):", l.remove(2)
   print l
   print "l.remove():", l.remove()
   print l
